백준 15666번

오늘 풀어본 문제는 백준의 15666번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 4

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

$N$ 개의 자연수와 자연수 $M$ 이 주어졌을 때, 아래 조건을 만족하는 길이가 $M$ 인 수열을 모두 구하는 프로그램을 작성하시오.

$N$ 개의 자연수 중에서 $M$ 개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
- 길이가 $K$ 인 수열 $A$ 가 $A_1 \leq A_2 \leq \cdots \leq A_{K-1} \leq A_K$를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 $N$ 과 $M$ 이 주어진다. $(1 \leq M \leq N \leq 8)$

둘째 줄에 $N$ 개의 수가 주어진다. 입력으로 주어지는 수는 $10,000$ 보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이과정

1번째 시도

문제를 보고 늘 보던 백트래킹 문제라는 것을 알 수 있었다. $N$과 $M$ 문제 시리즈는 푼 경험이 여러 번 있어왔기 때문이다.

$N$과 $M$ $(9)$ 문제의 코드를 살짝 수정하는 방식을 통해 문제를 해결할 수 있을 것이라고 생각했다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>
#include <unordered_set>

using namespace std;

int N, M;
vector<int> arr;

template <typename T>
struct vector_hash {
	size_t operator()(const std::vector<T>& v) const {
		std::hash<T> hasher;
		size_t seed = 0;
		for (const T& item : v) {
			seed ^= hasher(item) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
		}
		return seed;
	}
};

unordered_set<vector<int>, vector_hash<int>> vum;

void printNumbers(vector<int>& result, int i, int depth);

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    arr.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    
	sort(arr.begin(), arr.end());

	vector<int> result;
	printNumbers(result, 0, 0);

    return 0;
}

void printNumbers(vector<int>& result, int i, int depth) {
	if (depth == M) {
		if (vum.find(result) == vum.end()) {
			vum.insert(result);
			for (auto& elem : result) {
				cout << elem << " ";
			}
			cout << "\n";
		}
	}
	else {
		for (int j = i; j < N; j++) {
			result.emplace_back(arr[j]);
			printNumbers(result, j, depth + 1);
			result.pop_back();
		}
	}
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

너무 빡센 하루였다. 댄스 수업에서 온 힘을 다해서 춤을 추고 난 뒤 미분방정식 과제 듀를 맞추느라 이리저리 뛰어다녔다. 게다가 오고가고 하면서 비가 왔었는데 바람까지 불어서 잔뜩 얻어맞고 약간 감기가 걸린 것 같다.

머리가 잘 돌아가지 않을 것 같아 오늘은 실버 티어 문제릂 풀어서 올렸다. 그래도 나름 CLASS 4 문제라 스스로 정한 규칙은 어기지 않으면서도 현재 몸상태에서 할 수 있는 최선이었다.

이제 남은 실버 문제는 없으니 안심(?) 해도 좋다. 어디가 얼마나 아프건, 이제 골드 문제밖에 안 남았기 때문이다. 오늘의 날먹은 조금 봐줬으면 한다…

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/15666

← Previous Post Next Post →